package interview.huawei.tjt.training.dongtaiguihua;

import java.util.Scanner;

/**
 * 给定正整数 n，找到若干个完全平方数（比如 1, 4, 9, 16, ...）使得它们的和等于 n。你需要让组成和的完全平方数的个数最少。
 *
 * 给你一个整数 n ，返回和为 n 的完全平方数的 最少数量 。
 *
 * 完全平方数 是一个整数，其值等于另一个整数的平方；换句话说，其值等于一个整数自乘的积。例如，1、4、9 和 16 都是完全平方数，而 3 和 11 不是。
 *
 * 示例 1： 输入：n = 12 输出：3 解释：12 = 4 + 4 + 4
 *
 * 示例 2： 输入：n = 13 输出：2 解释：13 = 4 + 9
 *
 * 提示：
 *
 * 1 <= n <= 10^4
 */
public class NumSquares {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int[] dp = new int[n + 1];
        // 初始化
        for (int j = 0; j <= n; j ++) {
            dp[j] = Integer.MAX_VALUE;
        }
        dp[0] = 0;
//        // 先遍历物品，再遍历背包时
//        for (int i = 1; i * i <= n; i ++) {
//            for (int j = i * i; j <= n; j ++) {
//                if ( dp[j - i * i] != Integer.MAX_VALUE ) {
//                    dp[j] = Math.min(dp[j], dp[j - i * i] + 1);
//                }
//            }
//        }
        // 先遍历背包，再遍历物品时
        for (int j = 1; j <= n; j ++) {
            for (int i = 1; i * i <= j; i ++) {
                dp[j] = Math.min(dp[j], dp[j - i * i] + 1);
            }
        }
        System.out.println(dp[n]);
    }

}
